/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Exacto;
import java.util.ArrayList;
/**
 *
 * @author Colino
 */
public class Exacto {
       public static dgbi.BiGrafo res;
       
       public static int Exacto(dgbi.BiGrafo big)
       {
           ArrayList<dgbi.Node> V1=new ArrayList<dgbi.Node>();
           big.cantidadCruces();
           permuto(big.iv1/*V1*/, 0, big.iv1.size()-1,true, 0, big.v1/*fijos1*/, false, big.iv2/*v2*/, big.v2/*fijos2*/, V1);
           big.copiar(res);
           return res.cruces;
       }
       
      public static int permuto(ArrayList<dgbi.Node> arrV1, int dsd, int hst, boolean b, int veces, ArrayList<dgbi.Node> fijosV1, boolean esV2, ArrayList<dgbi.Node> arrV2, ArrayList<dgbi.Node> fijosV2, ArrayList<dgbi.Node> V1)
    {
        int i=dsd;
        dgbi.Node aux;
        while (i<hst+1)
        {
            if ((hst-dsd)==1)
            {
                dgbi.Node tmp;
                tmp=arrV1.get(hst);
                arrV1.set(hst, arrV1.get(dsd));
                arrV1.set(dsd, tmp);
                i++;
                // INTERCALA CON LOS ELEMENTOS FIJOS CON LA PERMUTACION Y CUENTA LA CANTIDAD DE CORTES
                if (esV2)
                {
                    ArrayList<dgbi.Node> caso= new ArrayList<dgbi.Node>();
                    int j=0;
                    int k=0;
                    while (j<fijosV1.size())
                    {
                        caso.add(j, fijosV1.get(j));
                        j++;
                    }
                    while (k<arrV1.size())
                    {
                        caso.add(j, arrV1.get(k));
                        j++;
                        k++;
                    }
                    int cantDsps=fijosV1.size();
                    if (cantDsps==0) // Esto es para que si la cantidad es cero no pase un -1 a intercalar
                        cantDsps++;
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new dgbi.BiGrafo(new ArrayList<dgbi.Node>(V1), new ArrayList<dgbi.Node>(caso));
                    }
                    else
                    {
                        dgbi.BiGrafo bg = new dgbi.BiGrafo(V1, caso);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res= new dgbi.BiGrafo(new ArrayList<dgbi.Node>(V1), new ArrayList<dgbi.Node>(caso));
                    }
                    intercalar(caso, 0, cantDsps-1, arrV2, fijosV2, true, V1);
                }
                else
                {
                    ArrayList<dgbi.Node> caso= new ArrayList<dgbi.Node>();
                    int j=0;
                    int k=0;
                    while (j<fijosV1.size())
                    {
                        caso.add(j, fijosV1.get(j));
                        j++;
                    }
                    while (k<arrV1.size())
                    {
                        caso.add(j, arrV1.get(k));
                        j++;
                        k++;
                    }
                    k=permuto(arrV2, 0, arrV2.size()-1, true, 0, fijosV2, true, arrV1, fijosV1, caso);
                    int cantDsps=fijosV1.size();
                    if (cantDsps==0) // Esto es para que si la cantidad es cero no pase un -1 a intercalar
                        cantDsps++;
                    intercalar(caso, 0, cantDsps-1, arrV2, fijosV2, false, caso);
                }
                veces++;
            }
            else
            {
                ArrayList<dgbi.Node> ref= new ArrayList<dgbi.Node>();
                int j=0;
                while (j<arrV1.size())
                {
                    ref.add(j, arrV1.get(j));
                    j++;
                }
                if (!esV2)
                {
                    veces=permuto(ref, dsd+1, hst, false, veces, fijosV1, false, arrV2, fijosV2, V1);                    
                }
                else
                {
                    veces=permuto(ref, dsd+1, hst, false, veces, fijosV1, true, arrV2, fijosV2, V1);
                }
                i++;
                if (i<hst+1)
                {
                    aux=arrV1.get(dsd);
                    arrV1.set(dsd, arrV1.get(i));
                    arrV1.set(i, aux);
                }
            }
        }
        return veces;
    }
    public static ArrayList<dgbi.Node> intercalar(ArrayList<dgbi.Node> instancia, int posicion, int cantDsps, ArrayList<dgbi.Node> instanciaV2, ArrayList<dgbi.Node> fijosV2, boolean esV2, ArrayList<dgbi.Node> vieneDeV1)
    {
        boolean primero=true;
        int pInicial,k; // contadores
        pInicial=posicion+1;
        k=posicion;
        dgbi.Node t;
        ArrayList<dgbi.Node> original= new ArrayList<dgbi.Node>();
        if (!esV2)
        {
            while (posicion<(instancia.size()-cantDsps-1))
            {
                if (cantDsps>0)
                {
                    instancia=intercalar(instancia, posicion+1, cantDsps-1, instanciaV2, fijosV2, esV2, vieneDeV1);
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<dgbi.Node>(instancia);
                        primero=false;
                    }
                    int veces=permuto(instanciaV2, 0, instanciaV2.size()-1, true, 0, fijosV2, true, instanciaV2, fijosV2, instancia);
                    posicion++;
                }
                else
                {
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<dgbi.Node>(instancia);
                        primero=false;
                    }
                    int veces=permuto(instanciaV2, 0, instanciaV2.size()-1, true, 0, fijosV2, true, instanciaV2, fijosV2, instancia);
                    posicion++;
                }
            }
        }
        else
        {
            while (posicion<(instancia.size()-cantDsps-1))
            {
                if (cantDsps>0)
                {
                    instancia=intercalar(instancia, posicion+1, cantDsps-1, instanciaV2, fijosV2, esV2, vieneDeV1);
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<dgbi.Node>(instancia);
                        primero=false;
                    }
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new dgbi.BiGrafo(new ArrayList<dgbi.Node>(vieneDeV1), new ArrayList<dgbi.Node>(instancia));
                    }
                    else
                    {
                        dgbi.BiGrafo bg = new dgbi.BiGrafo(vieneDeV1, instancia);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res= new dgbi.BiGrafo(new ArrayList<dgbi.Node>(vieneDeV1), new ArrayList<dgbi.Node>(instancia));
                    }
                    posicion++;
                }
                else
                {
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<dgbi.Node>(instancia);
                        primero=false;
                    }
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new dgbi.BiGrafo(new ArrayList<dgbi.Node>(vieneDeV1), new ArrayList<dgbi.Node>(instancia));
                    }
                    else
                    {
                        dgbi.BiGrafo bg = new dgbi.BiGrafo(vieneDeV1, instancia);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res=new dgbi.BiGrafo(new ArrayList<dgbi.Node>(vieneDeV1), new ArrayList<dgbi.Node>(instancia));
                    }
                    posicion++;
                }
            }
        }
        return original;
    }

}
